本场链接:Atcoder abc 174
闲话
本场F是个模板题,很谔谔.总体难度不高.
C.Repsept
题目大意:找一个最小的形如7777.....7777的数,使他是的倍数.如果无解则输出-1,反之只需输出位数即可.
数据范围:
思路
显然线性复杂度暴力枚举,如果超过了某个迭代次数则认为无解.正确性是由于会出现循环节,假如次数足够多则必然可以保证确实是无解而没有答案的.而每次迭代的时候,如果本次的数字是则下一次的数字就是.直到或次数过多停止.
代码
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
int main()
{
int k;cin >> k;
int a = 7,res = 0,ok = 1;
while(a % k != 0)
{
a = (a * 10 + 7) % k;
++res;
if(res == 1e7 + 7) break;
}
if(a % k == 0) cout << res+1;
else cout << -1;
return 0;
}
D.Alter Altar
题目大意:给定一个序列,要求每个R的左边不能是W.每次你可以执行两种操作中的一种,分别是交换序列里两个任意位置的元素,直接修改某个元素.问最少次数是多少,不需要具体方案.
思路
显然,最终要达到的情况形如RRRWWW.即所有的R都在左边,所有的W都在右边.由于每次交换都是任意的,所以直接统计所有的数量就可以知道把所有的R转移到最左边需要几次.由于直接修改的操作和交换事实上是对操作数量的影响是等价的,所以不需要管修改操作,只计算交换即可.
代码
#define _CRT_SECURE_NO_WARNINGS
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n;cin >> n;
string s;cin >> s;
int cnt = 0;
for(int i = 0;i < n;++i) cnt += (s[i] == 'R');
int res = 0;
for(int i = 0;i < cnt;++i)
{
if(s[i] == 'W')
++res;
}
cout << res << endl;
return 0;
}
E.Logs
题目大意:有个木棍,他们的长度给定.你可以砍次木棍,每次任选出一个木棍,并把他切成和两个长度,其中.问在进行次之后,所有的木棍中最长的最小值是多少.计算出答案后,如果是小数,则向上取整并输出一个整数.
数据范围:
思路
想法非常明显,典型的二分答案.答案.
考虑怎么写.设当前的答案是.如果的真定义为所有木棍砍完之后的最大值,则二分时如果为真,则应缩小范围,因为要最大值最小,既然这个是可以取到的,那么就应该缩小范围,去找到一个可能的更小的值作为答案.这样整个框架也就确定了.对于的条件判断来说,在里面遍历每一格根木棍的长度,要使最大值不超过,也就是要确定一个长度为的木棍最少要切几刀,这一点很显然就是看里包含几个,如果剩下的部分不足,显然不需要考虑,这就是下取整,即需要砍刀.最后看总刀数是不是的就可以了.
代码
const int N = 2e5+7;
const double eps = 1e-3;
int a[N],n,k;
bool check(double x)
{
int res = 0;
for(int i = 1;i <= n;++i)
{
res += floor(a[i] / x);
}
return res <= k;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;++i) cin >> a[i];
double l = 1,r = 1e9;
while(r - l > eps)
{
double mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
cout << (int)ceil(l);
return 0;
}
F.Range Set Query
题目大意:多组区间查询不同数的个数.
数据范围:
思路
莫队的模板题.如果不会莫队建议看这个博客,写的非常好.我在这里只简单说一下莫队算法是什么.
莫队本质上是在分块基础之上的,进一步的优化.首先是用两个指针表示当前查询的区间,并通过移动的方式更新当前的答案,其次再在离线的前提之下,将所有的查询进行排序,这样可以使指针的移动的次数处于一个比较稳定的状态.
还有一点,我的代码是没有卡常优化的,实际就差几十ms就TLE了.关于卡常也建议去看那个博客.加了优化之后大概快三倍左右.
我比赛的时候因为忘了空间开大导致WA了两发,就很蛋疼.
代码
const int N = 1e6+7;
int a[N],belong[N],cnt[N],res[N];
int quasize,bnum,now;
struct _Node
{
int l,r,id;
bool operator<(const _Node& b) const
{
if(belong[l] == belong[b.l]) return r < b.r;
return belong[l] < belong[b.l];
}
}q[N];
inline void del(int pos)
{
--cnt[a[pos]];
if(!cnt[a[pos]]) --now;
}
inline void add(int pos)
{
if(!cnt[a[pos]]) ++now;
++cnt[a[pos]];
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
quasize = sqrt(n);
bnum = ceil(double(n) / quasize);
for(int i = 1;i <= bnum;++i)
for(int j = (i - 1) * quasize + 1;j <= i * quasize;++j)
belong[j] = i;
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
for(int i = 1;i <= m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
sort(q+1,q+m + 1);
int l = 1,r = 0;
for(int i = 1;i <= m;++i)
{
int ql = q[i].l,qr = q[i].r;
while(l < ql) del(l++);
while(l > ql) add(--l);
while(r < qr) add(++r);
while(r > qr) del(r--);
res[q[i].id] = now;
}
for(int i = 1;i <= m;++i) printf("%d\n",res[i]);
return 0;
}